Data compression is an extremely useful tool for storing and transmitting large amounts of data. For example, the time required to transmit an image, such as a facsimile transmission of a document, is reduced drastically when compression is used to decrease the number of bits required to transmit the image. Many different data compression techniques exist in the prior art.
Every compression system is associated with a corresponding decompression system. The implementation of a decompression system can normally be inferred from the compression system. The algorithm used by the compression system to effectuate encoding must be either transmitted as part of the compressed document or inferable by the decompression system.
More specifically, in entropy coding, a sequence of "input" symbols&lt;t.sub.1, t.sub.2, t.sub.3 . . . , t.sub.m &gt;, which are typically data samples or quantized error values, can be replaced deterministically with a sequence of "output" codewords&lt;S.sub.1, S.sub.2, S.sub.3, . . . , S.sub.n &gt;as a function of time: EQU f(t)=(S)=&lt;S.sub.1, S.sub.2, . . . S.sub.n &gt;
such that a deterministic inverse (reconstruction) function exists: EQU f.sup.1 (S)=(t), for all {t},{S}=f({t})
This type of entropy code f may be built from a set of instantaneous production rules. The result of applying each of these rules is the generation of an ordered sequence of zero or more output tokens. However, the number of output tokens is usually one or more.
In some compression systems, an input file or set of data is translated into a sequence of decisions under the direction of a decision model. Each decision has an associated likelihood, and based on this likelihood, an output code is generated and appended to the compressed file. To implement these encoding systems, the compression systems have three parts: a decision model, a probability estimation method and a bit-stream generator. The decision model receives the input data and translates the data into a set of decisions which the compression system uses to encode the data. The probability estimation method is the procedure for developing the estimate for the likelihood of each decision. The bit-stream generator performs the final bit-stream encoding to generate the output code that is the compressed data set or compressed file.
Compression can effectively occur in either or both the decision model and the probability estimation method. For example, in Lempel-Ziv encoding, which is often used for text compression, the decision model is rather complicated and removes much redundancy. On the other hand, the probability estimation method and the bit-stream generator are usually trivial, where, for example, if 512 decision results are possible, each is assumed equally likely and the output bit pattern is always exactly nine bits in length. In contrast, a simple Huffman coder uses a trivial decision model with the compression being derived from the probability estimation method "knowing" the usual frequencies of the letters in text files and generating bit output appropriately. Similarly, redundancy can be reduced dramatically from digital time signals using Karhunen-Loeve type transforms or even simple subtraction as utilized in differential pulse code modulation. However, in these situations, the probability estimation method and bit-stream generator are necessary in order to realize redundancy reduction. For more information on Lempel-Ziv, Huffman, and Karhunen-Loeve, see Thomas Lynch, Data Compression Techniques Applications, (1985 Van Nostrand Reinhold) and Mark Nelson, The Data Compression Book (1992 M & T Publishing, Inc.)
In other methods, such as CCITT facsimile transmission, redundancy is reduced initially using a simple predictive method like exclusive-oring a line with the previous line. Then, a decision model replaces each line with a sequence of all-black or all-white run lengths. Afterwards, further compression can be achieved by subjecting the result to a Huffman-like code using default probability estimates.
One compression technique widely employed is arithmetic coding. Arithmetic coding maps a string of data (i.e., a "message") to a code string in such a way that the original message can be recovered from the code string wherein the encoding and decoding algorithms perform arithmetic operations on the code string. For a discussion on arithmetic coding see, Glenn G. Langdon, Jr., "An Introduction to Arithmetic Coding", IBM Journal of Research and Development, vol. 28, no. 2, (March 1984).
In arithmetic coding, the code representative of a message is represented by an interval of numbers between 0 and 1. As the number of symbols in the message increases, the interval representing it becomes smaller and the number of bits needed to specify that interval increases. Initially, the interval for the message is between zero and one [0,1). As each symbol of the message is processed, the interval is narrowed in accordance with the symbol probability.
For example, referring to FIG. 1 a, the symbols (in this instance, text)z, y, x, w, v, u 79are assigned the probabilities 0.2, 0.3, 0.1, 0.2, 0.1, 0.1. The probabilities are then mapped to the range of [0,1.0) resulting in the ranges identified in FIG. 1a. Referring to FIG. 1a, the symbol z is allocated the range [0, 0.2) reflecting the probability of 0.2 and the symbol u is allocated the range of [.9, 1.0) reflecting the high end of the probability range of symbols and the u probability of 0.1.
In order for compression to be possible, the symbols which occur more frequently are assigned a greater probability value. Once the probability ranges are allocated, the symbols may be encoded for compression. The initial range or interval is set to [0, 1). After the occurrence of the first symbol of the message to be compressed, the range is narrowed in proportion to that symbol's probability. Referring to FIG. 1a, the range [0, 1) is first illustrated. After the occurrence of the symbol y, the range is decreased to a new interval of size proportional to the probability of y. In other words, instead of the range or interval being set to its initial values, the range is set according to the probability of the symbol which just occurred. Since the probability of y is 0.3 and has a range of [0.2, 0.5), the updated range from which the encoding occurs is [0.2, 0.5), such that the probability of occurrence of the next symbol includes the influence of the probabilities of the symbols which came before it (i.e., y). Thus, all of the probabilities for the symbols total a range from 0.2 to 0.5 instead of 0 to 1 as before the occurrence of the symbol y. Similarly, after the occurrence of the next symbol z, which has the probability of 0.2 and the range [0, 0.2) the interval is decreased in proportion to the z probability to [0.2, 0.26), such that the range of probabilities for the next symbol is taken from the interval 0.2 to 0.26, with the influence of both the previous y and z symbols taken into account.
In decoding, since the size of the interval used in the encoding process is indicative of the probability range of a symbol in group of symbols, the symbols can be easily extracted, using the ranges for each symbol that were utilized in encoding. For example, if the final interval was [0.23, 0.236), one can determine that the first symbol is y because the final interval lies completely within the range of y [0.2, 0.5). Using the same process as the encoder, after seeing y, the initial interval [0,1) is updated to be [0.2, 0.5) and the updated range of a [0.2, 0.26) encompasses the final interval [0.23, 0.236). This process continues until all symbols are decoded.
A binary arithmetic coder is one type of an arithmetic coding system. In a binary arithmetic coding system, the selection of a symbol from a set of symbols can be encoded as a sequence of binary decisions. An example of a binary arithmetic coder is the "Q-coder" developed at International Business Machines, Armonk, N.Y. The Q-coder utilizes fixed precision arithmetic and a renormalization process wherein the code string and interval are renormalized as necessary in order to maintain the values within the bounds allowed by fixed-precision representation. In addition, to avoid the need to perform a multiplication operation to scale the interval to reflect the coding of a symbol, an approximation is utilized in place of the multiplication. For information regarding the Q-coder, see: W. B. Pennebaker, J. L. Mitchell, G. G. Langdon, F., Jr., R. B. Arps, "An Overview of the Basic Principles of the Q-Coder Adaptive binary Arithmetic Coder", IBM Journal of Research and Development, vol. 32, no. 6, November 1988, pp. 717-726; J. L. Mitchell, W. B. Pennebaker, "Optimal Hardware and Software Arithmetic Coding Procedures for the Q-Coder", IBM, Journal of Research and Development, vol. 32, no. 6, November 1988, pp. 727-736; W. B. Pennebaker, J. L. Mitchell, "Probability Estimation for the Q-Coder", IBM Journal of Research and Development, vol. 32, no. 6, November 1988, pp. 753-774. For further discussion of data compression, see: Timothy C. Bell, John G. Cleary, Ian H. Whitten, Text Compression(1990 Prentice Hall Inc.); and Anil K. Jain, Fundamentals of Digital Image Processing, (1989 Prentice Hall, Inc.).
As will be shown, the present invention uses a decision model which produces decisions which are always two-valued (i.e., yes or no). The present invention also employs output tokens which are not fixed-length bit strings. In particular, the present invention encodes most decisions with less than one bit.